package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * https://leetcode.com/problems/merge-intervals/
 * 区间合并
 * 又有点像俄罗斯套娃信封的 LIS,耐心排序
 * https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/qu-jian-wen-ti-he-ji
 * <p>
 * TODO 也可以用连通图的思想来解
 * https://leetcode.com/problems/merge-intervals/solution/
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC56 implements ArrayProblem {

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        List<int[]> result = new ArrayList<>();
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0], right = intervals[i][1];
            while (i + 1 < intervals.length && intervals[i + 1][0] <= right) {
                right = Math.max(right, intervals[i + 1][1]);
                i++;
            }
            i++;
            result.add(new int[]{left, right});
        }
        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] a = {{1, 3}, {8, 10}, {15, 18}, {2, 6}};
        System.out.println(Arrays.deepToString(new LC56().merge(a)));
    }
}
